11070. Хорошие старые времена

Имеется строка из не более 255 символов, содержащая действительные числа и знаки арифметических операций (+, -, *, /). Необходимо вычислить значение выражения, заданного в строке.

Вход. Каждая строка содержит арифметическое выражение. Операции ‘+’ и ‘-‘ могут быть как бинарными, так и унарными. Строка не содержит пробелов, табуляций и скобок.

Выход. Для каждого выражения вывести его значение с тремя точками после запятой.

Пример входа

1/2/2

-3.0

3

4.0+3.0/5.0

1*2*3+1+1*2+1*2*3*4

Пример выхода

0.250

-3.000

3.000

4.600

33.000

РЕШЕНИЕ

синтаксический анализ

Анализ алгоритма

Для решения задачи следует произвести интерпретацию входного выражения. Запишем грамматику для вычисления арифметического выражения:

S ® S + T | S - T | T

T ® T * F | T / F | F

F ® +F | -F | G

G ® <действительное число>

Преобразуем грамматику в не леворекурсивную (e – пустое слово):

S ® TS1

S1 ® +TS1 | -TS1 | e

T ® FT1

T1 ® *FT1 | /FT1 | e

F ® +F | -F | G

G ® <действительное число>

Реализация алгоритма

Объявим рабочие переменные a и b, стек Stack для интерпретации выражений и строку stroka, в которую будем заносить входное выражение:

char stroka[256];

stack<double> Stack;

int len, ptr;

double a, b;

Каждому нетерминальному символу не леворекурсивной грамматики поставим в соответствие процедуру. Каждое правило грамматики выпишем отдельной процедурой. Выпишем объявления процедур, так как они взаимно вызывают друг друга.

void s1(void);

void t1(void);void t(void);

void f(void); void g(void);

void s(void)

{

t(); s1();

}

void s1(void)

{

if (stroka[ptr] == '+')

{

ptr++; t();

a = Stack.top(); Stack.pop();

b = Stack.top(); Stack.pop();

Stack.push(a+b);

s1();

}

if (stroka[ptr] == '-')

{

ptr++; t();

a = Stack.top(); Stack.pop();

b = Stack.top(); Stack.pop();

Stack.push(b-a);

s1();

}

}

void t(void)

{

f(); t1();

}

void t1(void)

{

if (stroka[ptr] == '*')

{

ptr++; f();

a = Stack.top(); Stack.pop();

b = Stack.top(); Stack.pop();

Stack.push(a*b);

t1();

}

if (stroka[ptr] == '/')

{

ptr++; f();

a = Stack.top(); Stack.pop();

b = Stack.top(); Stack.pop();

Stack.push(b/a);

t1();

}

}

void f(void)

{

if (stroka[ptr] == '+')

{

ptr++; f();

} else if (stroka[ptr] == '-')

{

ptr++; f();

a = Stack.top(); Stack.pop();

Stack.push(-a);

} else g();

}

void g(void)

{

double n;

sscanf(stroka+ptr,"%lf",&n);

Stack.push(n);

while(isdigit(stroka[ptr]) || (stroka[ptr] == '.')) ptr++;

}

Основная часть программы. Выражение читаем в строку stroka, текущий указатель разбора выражения ptr устанавливаем в 0. После вычисления выражения (вызова функции s) выводим результат, который находится на вершине стека.

while(gets(stroka))

{

ptr = 0; s();

printf("%.3lf\n",Stack.top());

}